package ljl.alg.jianzhioffer.round3.medium;

import java.util.ArrayDeque;
import java.util.Deque;

public class _33_verifyPostorder {

    /**
     * 过了，我自己写的，懂？
     * */
    class my {
        /*
         * 最后一个元素是根，往左找
         * 都比他大的是右孩子，
         * 再往左，全比他小，是左孩子，
         * 如果都小，ok，递归找；如果有大的，false
         * */
        public boolean verifyPostorder(int[] postorder) {
            return check(postorder, 0, postorder.length - 1);
        }
        boolean check(int[] post, int from, int to) {
            if (from >= to) return true;
            int mid = to;
            while (mid - 1 >= from && post[mid - 1] > post[to]) {
                mid--;
            }
            boolean pass = true;
            if (mid < to)
                pass = check(post, mid, to - 1);
            if (!pass)
                return false;
            int p = mid;
            while (p - 1 >= from)
                if (post[--p] > post[to])
                    return false;
            if (p < mid)
                pass = check(post, from, mid - 1);
            return pass;
        }
    }

    /**
     * 这个比我的稍微慢点（1ms） 但是很优雅
     * */
    class fufei {

        public boolean verifyPostorder(int[] postorder) {
            return test(postorder, 0, postorder.length - 1);
        }
        private boolean test(int[] post, int from, int to) {
            if (from >= to) return true;
            int i = from;
            while (post[i] < post[to]) i++;
            int m = i;
            while (post[m] > post[to]) m++;
            return m == to && test(post, from, m - 1) && test(post, m, to - 1);
        }
    }

    class lufei2 {
        public boolean verifyPostorder(int[] postorder) {
            Deque<Integer> stack = new ArrayDeque<>();
            int root = Integer.MAX_VALUE;
            for (int i = postorder.length - 1; i >= 0 ; i--) {
                if (postorder[i] > root) return false;
                while (!stack.isEmpty() && stack.peek() > postorder[i])
                    root = stack.pop();
                stack.push(postorder[i]);
            }
            return true;
        }
    }

}
